/*
 * @lc app=leetcode.cn id=726 lang=typescript
 *
 * [726] 原子的数量
 */

// @lc code=start
function countOfAtoms(formula: string): string {
  // 看见右括号，入栈次数
  const stack = [1];
  // 保存原子出现的总次数
  const hash: Map<string, number> = new Map();

  let i = formula.length - 1;
  let count = '';
  let lowerChar = '';
  while (i >= 0) {
    const char = formula[i];
    if (char >= '0' && char <= '9') {
      count = char + count;
    } else if (char >= 'a' && char <= 'z') {
      lowerChar = char + lowerChar;
    } else if (char === ')') {
      stack.push(stack[stack.length - 1] * Number(count || '1'));
      count = '';
    } else if (char === '(') {
      stack.pop();
    } else {
      let atom = char + lowerChar;
      hash.set(atom, (hash.get(atom) || 0) + stack[stack.length - 1] * Number(count || '1'));
      lowerChar = count = '';
    }
    i--;
  }
  // 按照字典序排序
  const atoms = Array.from(hash);
  atoms.sort((a, b): number => {
    if (a[0] < b[0]) return -1;
    if (a[0] < b[0]) return 1;
    return 0;
  });
  // 更新结果
  let ans = '';
  for (let [char, count] of atoms) {
    ans += char;
    if (count > 1) {
      ans += String(count);
    }
  }

  return ans;
}
// @lc code=end
